#include <string.h>
#include <stdlib.h>
#include "gdl_types.h"
#include "gdl_list.h"

GDL_List* gdl_list_alloc(void)
{
	unsigned list_size = sizeof(GDL_List);
	GDL_List *list = malloc(list_size);
		
	if( list ){
		memset(list, 0, list_size);
		list -> data = NULL;
		list -> next = NULL;
		list -> prev = NULL;
	}

	return list;
}

/**
 * gdl_list_free: 
 * @list: a #GDL_List
 *
 * Frees all of the memory used by a #GDL_List.
 */
void gdl_list_free (GDL_List *list)
{
	GDL_List *cur = NULL;

	while( list ){
		cur = list;
		list = list -> next;
		free(cur);
	}		
}

/**
 * gdl_list_append:
 * @list: a pointer to a #GDL_List
 * @data: the data for the new element
 *
 * Adds a new element on to the end of the list.
 *
 * <note><para>
 * The return value is the new start of the list, which 
 * may have changed, so make sure you store the new value.
 * </para></note>
 *
 * <note><para>
 * Note that gdl_list_append() has to traverse the entire list 
 * to find the end, which is inefficient when adding multiple 
 * elements. A common idiom to avoid the inefficiency is to prepend 
 * the elements and reverse the list when all elements have been added.
 * </para></note>
 * 
 * Returns: the new start of the #GDL_List
 */
GDL_List* gdl_list_append(GDL_List *list, gdl_any_pointer data)
{
	GDL_List *new_list;
	GDL_List *last;

	new_list = gdl_list_alloc();
	new_list -> data = data;

	if( list ){
		last = gdl_list_last(list);
		last -> next = new_list;
		new_list -> prev = last;

		return list;
	}else{
		return new_list;
	}
}


/**
 * gdl_list_last:
 * @list: a #GDL_List
 *
 * Gets the last element in a #GDL_List.
 *
 * Returns: the last element in the #GDL_List, 
 *     or %NULL if the #GDL_List has no elements
 */
GDL_List* gdl_list_last(GDL_List *list)
{
	if( list ){
		while( list -> next ){
			list = list -> next;
		}
	}

	return list;
}

/**
 * gdl_list_prepend:
 * @list: a pointer to a #GDL_List
 * @data: the data for the new element
 *
 * Adds a new element on to the start of the list.
 *
 * <note><para>
 * The return value is the new start of the list, which 
 * may have changed, so make sure you store the new value.
 * </para></note>
 *
 * |[ 
 * /&ast; Notice that it is initialized to the empty list. &ast;/
 * GDL_List *list = NULL;
 * list = gdl_list_prepend (list, "last");
 * list = gdl_list_prepend (list, "first");
 * ]|
 *
 * Returns: the new start of the #GDL_List
 */
GDL_List* gdl_list_prepend(GDL_List *list, gdl_any_pointer data)
{
	GDL_List *new_list;

	new_list = gdl_list_alloc();
	new_list -> data = data;
	new_list -> next = list;

	if( list ){
		new_list -> prev = list -> prev;
		if( list -> prev ){
			list -> prev -> next = new_list;
		}
		list -> prev = new_list;
	}else{
		new_list -> prev = NULL;
	}

	return new_list;
}

/**
 * gdl_list_insert:
 * @list: a pointer to a #GDL_List
 * @data: the data for the new element
 * @position: the position to insert the element. If this is 
 *     negative, or is larger than the number of elements in the 
 *     list, the new element is added on to the end of the list.
 * 
 * Inserts a new element into the list at the given position.
 *
 * Returns: the new start of the #GDL_List
 */
GDL_List* gdl_list_insert(GDL_List *list, gdl_any_pointer data, int position)
{
	GDL_List *new_list;
	GDL_List *tmp_list;

	if( position < 0 ){
		return gdl_list_append(list, data);
	}else if (position == 0){
		return gdl_list_prepend(list, data);
	}

	tmp_list = gdl_list_nth(list, position);
	if( !tmp_list ){
		return gdl_list_append(list, data);
	}

	new_list = gdl_list_alloc();
	new_list -> data = data;
	new_list -> prev = tmp_list -> prev;
	if( tmp_list -> prev ){
		tmp_list -> prev -> next = new_list;
	}
	new_list -> next = tmp_list;
	tmp_list -> prev = new_list;

	if( tmp_list == list ){
		return new_list;
	}else{
		return list;
	}
}

/**
 * gdl_list_nth:
 * @list: a #GDL_List
 * @n: the position of the element, counting from 0
 *
 * Gets the element at the given position in a #GList.
 *
 * Returns: the element, or %NULL if the position is off 
 *     the end of the #GDL_List
 */
GDL_List* gdl_list_nth(GDL_List *list, unsigned n)
{
	while( (n-- > 0) && list ){
		list = list -> next;
	}

	return list;
}

static GDL_List* gdl_list_insert_sorted_real(GDL_List *list, 
					     gdl_any_pointer data, 
					     GDL_Func func, 
					     gdl_any_pointer user_data)
{
	GDL_List *tmp_list = list;
	GDL_List *new_list;
	int cmp;

	if( !list ){
		new_list = gdl_list_alloc();
		new_list -> data = data;
		return new_list;
	}

	cmp = ((GDL_Compare_Data_Func) func)(data, 
					     tmp_list -> data, 
					     user_data);

	while( (tmp_list -> next) && (cmp > 0) ){
		tmp_list = tmp_list -> next;
		cmp = ((GDL_Compare_Data_Func) func)(data, 
						     tmp_list -> data, 
						     user_data);
	}

	new_list = gdl_list_alloc();
	new_list -> data = data;

	if( (!tmp_list -> next) && (cmp > 0) ){
		tmp_list -> next = new_list;
		new_list->prev = tmp_list;
		return list;
	}

	if( tmp_list -> prev ){
		tmp_list -> prev -> next = new_list;
		new_list -> prev = tmp_list -> prev;
	}
	new_list -> next = tmp_list;
	tmp_list -> prev = new_list;

	if( tmp_list == list ){
		return new_list;
	}else{
		return list;
	}
}

/**
 * gdl_list_insert_sorted:
 * @list: a pointer to a #GDL_List
 * @data: the data for the new element
 * @func: the function to compare elements in the list. It should 
 *     return a number > 0 if the first parameter comes after the 
 *     second parameter in the sort order.
 *
 * Inserts a new element into the list, using the given comparison 
 * function to determine its position.
 *
 * Returns: the new start of the #GDL_List
 */
GDL_List* gdl_list_insert_sorted(GDL_List *list, gdl_any_pointer data, GDL_Compare_Func  func)
{
	return gdl_list_insert_sorted_real(list, data, (GDL_Func)func, NULL);
}
